#ifndef TREE_OF_CLUSTERS_H
#define TREE_OF_CLUSTERS_H

#include "Cluster.h"
#include "Graph.h"
#include "CT_Types.h"
#include <boost/unordered_map.hpp>
#include <stack>

// This class manages a tree of clusters.
// It also has an associated CT graph (a graph of clusters)

class Tree_Of_Clusters {
public:
    Tree_Of_Clusters();
    virtual ~Tree_Of_Clusters();
    Tree_Of_Clusters(const Tree_Of_Clusters& other);

    void destroy();
    void set_root(Cluster *root_cluster);
    void make_family(Cluster *parent, Cluster *L, Cluster *R);

    void set_children(Cluster *parent, Cluster *L, Cluster *R);
    void set_parent  (Cluster *parent, Cluster *L, Cluster *R);

    ct_graph_t* to_graph();
    void init_from_graph(ct_graph_t& graph,
                         std::vector<Cluster*> nodes);

    void write(std::string& file_name);
    void write(std::ostream& os);
    void write_nodes(std::string& file_name);

    void replace_cluster(Cluster *old_one, Cluster *new_one);
    void delete_cluster(Cluster *victim);

    void push_clusters(Cluster *a, Cluster *b, Cluster *parent);
    void pop_clusters(Cluster*& a, Cluster*& b);
    void push_tree_nodes(Cluster *root);
    void push_tree_nodes(Tree_Of_Clusters& subtree);

    void preorder_write(std::ostream& os);
    void preorder_write(std::ostream& os, Tree_Node *root);
    void set_leaf_distances();
    void set_leaf_distances(Cluster *root);

    Cluster *root;

private:
    // internal methods.
    void delete_tree(const Cluster *root);
    Cluster *copy_tree(const Cluster *root);
    void add_vertex_to_graph(Cluster *n, ct_graph_t& graph) const;
    void add_edges_to_graph(int parent_ID, Cluster *n, ct_graph_t& graph) const;
    ct_vertex_t null_vertex;
    std::vector<Cluster*> enumerate_nodes();
//    boost::unordered_map<int, Cluster*> ID_to_node;
    std::stack<Cluster*> pending_clusters;

    bool leaf_distances_stale;
    Cluster_Metric cluster_metric;
};

template<class Funct>
void preorder(Cluster *root, Funct& functor);


#endif
